#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define Size 5

//定义链表结构体
typedef struct Link
{
    //数据域
    int elem;
    //指针
    struct Link *next;
} link;

link *initLink(link *head)
{
    link *temp = (link *)malloc(sizeof(link));
    temp->elem = 1;
    temp->next = NULL;
    head = temp;
    for (int i = 2; i <= Size; i++)
    {
        link *new = (link *)malloc(sizeof(link));
        new->elem = i;
        new->next = NULL;
        temp->next = new;
        temp = new;
    }

    return head;
}

void *displayLink(link *head)
{
    while (head->next)
    {
        printf(" %d ", head->elem);
        head = head->next;
    }
    printf(" %d \n", head->elem);
}

link *lastNode(link *head)
{
    while (head->next)
    {
        head = head->next;
    }
    return head;
}

char link_is_intersect_interation(link *linkOne, link *linkTwo)
{
    char i = 1;
    while (linkOne->next)
    {
        i++;
        link *temp = linkTwo;
        while (linkTwo->next)
        {
            if (linkOne->next == linkTwo->next)
            {
                return i;
            }

            linkTwo = linkTwo->next;
        }
        linkOne = linkOne->next;
        linkTwo = temp;
    }

    return 0;
}

bool link_is_intersect_tail(link *linkOne, link *linkTwo)
{
    while (linkOne)
    {
        if (linkOne->next)
        {
            linkOne = linkOne->next;
        }
        else
        {
            break;
        }
    }

    while (linkTwo)
    {
        if (linkTwo->next)
        {
            linkTwo = linkTwo->next;
        }
        else
        {
            break;
        }
    }

    return (linkOne == linkTwo);
}

bool link_is_intersect_short_link_compare(link *linkOne, link *linkTwo)
{
    // 1.获取两个链表的长度,lenOne,lenTwo
    // 2.取较短的那个链表的长度作为两个链表对比的基准
    // 3.取较长的那个链表的基准长度的链表
    // 4.逐个对比基准链表的节点是否相同
    int lenOne = 0, lenTwo = 0, setup = 0;
    link *linkLong = NULL, *linkShort = NULL;

    linkLong = linkOne;
    while (linkLong->next)
    {
        lenOne++;
        linkLong = linkLong->next;
    }

    linkShort = linkTwo;
    while (linkShort->next)
    {
        lenTwo++;
        linkShort = linkShort->next;
    }

    if (lenOne > lenTwo)
    {
        setup = lenTwo;
        linkLong = linkOne;
        linkShort = linkTwo;
    }
    else if (lenOne == lenTwo)
    {
        setup = 0;
        linkLong = linkOne;
        linkShort = linkTwo;
    }
    else
    {
        setup = lenOne;
        linkLong = linkTwo;
        linkShort = linkOne;
    }

    //截取长的链表
    while (setup)
    {
        linkLong = linkLong->next;
        setup--;
    }

    //逐个对比链表
    while (linkLong->next)
    {
        link *temp = linkShort;
        while (temp->next)
        {
            if (linkLong->next == temp->next)
            {
                return true;
            }
            temp = temp->next;
        }
        temp = linkShort;
        linkLong = linkLong->next;
    }

    return false;
}

int main()
{
    printf("link 1: \n");
    link *headOne = NULL;
    //初始化链表
    headOne = initLink(headOne);
    displayLink(headOne);

    printf("link 2: \n");
    link *headTwo = NULL;
    //初始化链表
    headTwo = initLink(headTwo);
    displayLink(headTwo);

    //使两个链表的第6个元素相交
    link *sixNode = (link *)malloc(sizeof(link));
    sixNode->elem = 6;
    sixNode->next = NULL;

    //把两个链表的第6个节点指向同一个节点
    link *oneLast = lastNode(headOne);
    link *twoLast = lastNode(headTwo);
    oneLast->next = sixNode;
    twoLast->next = sixNode;

    printf("为两个链表添加了同样的第6个节点: \n");
    displayLink(headOne);
    displayLink(headTwo);
    char isEqual = (oneLast->next == twoLast->next);
    printf("直接判断:两个链表的第6个节点是否相等: %d \n", isEqual);

    // todo 两个链表是否相交
    char check = link_is_intersect_interation(headOne, headTwo);
    if (check > 0)
    {
        printf("迭代判断:两个链表的第%d个节点是相交的 \n", check);
    }
    else
    {
        printf("迭代判断:两个链表的节点没有相交的\n");
    }

    bool checkRes = link_is_intersect_tail(headOne, headTwo);
    if (check)
    {
        printf("尾巴判断:两个链表有节点是相交的 \n");
    }
    else
    {
        printf("尾巴判断:两个链表的节点没有相交的\n");
    }

    link *sevenNode = (link *)malloc(sizeof(link));
    sevenNode->elem = 7;
    sevenNode->next = NULL;
     twoLast = lastNode(headTwo);
    twoLast->next = sevenNode;

    link *eightNode = (link *)malloc(sizeof(link));
    eightNode->elem = 8;
    eightNode->next = NULL;
     twoLast = lastNode(headTwo);
    twoLast->next = eightNode;

    bool checkResAndFinally = link_is_intersect_short_link_compare(headOne, headTwo);
    if (checkResAndFinally)
    {
        printf("短链对比法判断:两个链表有节点是相交的 \n");
    }
    else
    {
        printf("短链对比法判断:两个链表的节点没有相交的\n");
    }

    return 0;
}